package greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class GreedyAlgorithm {
    public static void main(String[] args) {
        //存储电台
        HashMap<String, HashSet<String>> broadCasts = new HashMap<>();
        HashSet<String> hashSet1 = new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");
        HashSet<String> hashSet2 = new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");
        HashSet<String> hashSet3 = new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");
        HashSet<String> hashSet4 = new HashSet<>();
        hashSet4.add("上海");
        hashSet4.add("天津");
        HashSet<String> hashSet5 = new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");
        broadCasts.put("K1", hashSet1);
        broadCasts.put("K2", hashSet2);
        broadCasts.put("K3", hashSet3);
        broadCasts.put("K4", hashSet4);
        broadCasts.put("K5", hashSet5);
        //存储还没有被覆盖的地区
        HashSet<String> areasAll = new HashSet<>();
        areasAll.addAll(hashSet1);
        areasAll.addAll(hashSet2);
        areasAll.addAll(hashSet3);
        areasAll.addAll(hashSet4);
        areasAll.addAll(hashSet5);
        //存储已经被挑选的电台
        ArrayList<String> selects = new ArrayList<>();
        //设置一个临时变量，存储遍历过程中最多覆盖地区的电台名字
        String maxKey;
        int maxSize;
        while (areasAll.size() > 0) {
            maxKey = null;
            maxSize = 0;
            for (String broadCast : broadCasts.keySet()) {
                //得到当前最大可覆盖的地区数量
                if (maxKey != null) {
                    HashSet<String> maxAreas = broadCasts.get(maxKey);
                    maxAreas.retainAll(areasAll);
                    maxSize = maxAreas.size();
                }
                //获得当前遍历到的节点的能覆盖的所有地区
                HashSet<String> areas = broadCasts.get(broadCast);
                //保留重复的地区
                areas.retainAll(areasAll);
                if (areas.size() > 0 && (maxKey == null || areas.size() > maxSize)) {
                    maxKey = broadCast;
                }
            }
            if (maxKey != null) {
                selects.add(maxKey);
                areasAll.removeAll(broadCasts.get(maxKey));
                broadCasts.remove(maxKey);
            }

        }
        System.out.println(selects);

    }

}
